#include <iostream>
#include <algorithm>
#include <ctime>
#include "BinarySearchTree.h"
using namespace std;

template <typename Comparable>
void BSTSorting(vector<Comparable> &_arr, int _mode)
{
    BinarySearchTree<Comparable> T;
    //当_mode为0时，直接排序，利用二叉树的排序方法，将数据依次
    //存到二叉树中，再按顺序取出，即可完成排序。
    if(_mode==0){
        for(int i=0;i<_arr.size();i++){
            T.insert(_arr[i]);
        }
        for(int i=0;i<_arr.size();i++){
            Comparable t = T.findMin();
            _arr[i] = t;
            T.remove(t);
        }
    }
    //当_mode为1时，先利用random_shuffle函数进行乱序，
    //之后利用同样方法用二叉树的方式进行排序。
    else if(_mode==1){
        //用srand提前更改随机种子，防止每次乱序后的结果都相同。
        srand(time(0)); 
        //调用随机函数进行数组乱序。
        random_shuffle(_arr.begin(),_arr.end());
        for(int i=0;i<_arr.size();i++){
            T.insert(_arr[i]);
        }
        for(int i=0;i<_arr.size();i++){
            Comparable t = T.findMin();
            _arr[i] = t;
            T.remove(t);
        }
    }
}


int main()
{
    //这一部分是对二叉树的一些基本功能函数的测试。
    BinarySearchTree<int> A;

    //测试insert和remove函数。
    for(int i=0;i<=100;i=i+5)
    {
        A.insert(i);
    }
    for(int i=5;i<=95;i=i+10)
    {
        A.remove(i);
    }
    A.printTree();   //输出当前的二叉树A。
 
    //测试findMax和findMin函数。
    cout << "The maximal value is:";
    cout << A.findMax() <<endl;
    cout << "The minimal value is:";
    cout << A.findMin() << endl;
  
    //测试contains函数。
    int value;
    cout << "Enter the value you want to find:";
    cin >> value;
    if(A.contains(value)){
        cout << "The target value can be found." << endl;
    }
    else{
        cout << "The target value can't be found." << endl;
    }  
    
    A.makeEmpty();  //清空二叉树，并检验是否清空。
    A.printTree();   

    //这一部分是对于自定义的函数BSTSorting进行测试，定义两个数组，
    //分别测试_mode为0和_mode为1的两种情况。
    vector<int> arr1 = {4,2,6,0,1,8,9,3,7,5};
    vector<int> arr2 = {4,8,18,6,0,10,16,2,14,12};

    //_mode=0时，正常排序。
    BSTSorting(arr1,0);     
    for(int i=0;i<10;i++){
        cout << arr1[i] << " ";
    }
    cout << endl;

    //_mode=1时，先乱序后排序。
    BSTSorting(arr2,1);
    for(int i=0;i<10;i++){
        cout << arr2[i] << " ";
    } 
    cout << endl; 

    //这一部分是对于BSTSorting函数中_mode=0情况的最坏效率测试。
    vector<int> t1(5000);
    vector<int> t2(10000);
    vector<int> t3(15000);
    vector<int> t4(20000);
    for(int i=0;i<5000;i++){
        t1[i] = 4999-i;
    }
    for(int i=0;i<10000;i++){
        t2[i] = 9999-i;
    }
    for(int i=0;i<15000;i++){
        t3[i] = 14999-i;
    }
    for(int i=0;i<20000;i++){
        t4[i] = 19999-i;
    }

    //在每次调用BSTSorting函数前后读取时间信息，通过作差得到运行时间。
    clock_t begintime1 = clock();
    BSTSorting(t1,0);
    clock_t endtime1 = clock();
    cout << "The running time of the sorting of the array t1 is:" << double(endtime1 - begintime1) / CLOCKS_PER_SEC << "s" << endl;
    clock_t begintime2 = clock();
    BSTSorting(t2,0);
    clock_t endtime2 = clock();
    cout << "The running time of the sorting of the array t2 is:" << double(endtime2 - begintime2) / CLOCKS_PER_SEC << "s" << endl;   
    clock_t begintime3 = clock();
    BSTSorting(t3,0);
    clock_t endtime3 = clock();
    cout << "The running time of the sorting of the array t3 is:" << double(endtime3 - begintime3) / CLOCKS_PER_SEC << "s" << endl;
    clock_t begintime4 = clock();
    BSTSorting(t4,0);
    clock_t endtime4 = clock();
    cout << "The running time of the sorting of the array t4 is:" << double(endtime4 - begintime4) / CLOCKS_PER_SEC << "s" << endl;

    //这一部分是对于BSTSorting函数中_mode=1情况的平均效率测试。
    vector<int> p1(1000);
    vector<int> p2(2000);
    vector<int> p3(5000);
    vector<int> p4(10000);
    for(int i=0;i<1000;i++){
        p1[i] = i;
    }
    for(int i=0;i<2000;i++){
        p2[i] = i;
    }
    for(int i=0;i<5000;i++){
        p3[i] = i;
    }
    for(int i=0;i<10000;i++){
        p4[i] = i;
    }

    //对于每个数组同时运行3000次BSTSorting函数，同样通过读取
    //运行前后的时间，通过作差取平均得到平均运行时间。
    clock_t begin_time1 = clock();
    for(int i=0;i<3000;i++){
        BSTSorting(p1,1);
    }
    clock_t end_time1 = clock();
    cout << "The average running time of the sorting of p1 is:" << double(end_time1-begin_time1) / (3000*CLOCKS_PER_SEC) << "s" << endl;
    clock_t begin_time2 = clock();
    for(int i=0;i<3000;i++){
        BSTSorting(p2,1);
    }
    clock_t end_time2 = clock();
    cout << "The average running time of the sorting of p2 is:" << double(end_time2-begin_time2) / (3000*CLOCKS_PER_SEC) << "s" << endl;
    clock_t begin_time3 = clock();
    for(int i=0;i<3000;i++){
        BSTSorting(p3,1);
    }
    clock_t end_time3 = clock();
    cout << "The average running time of the sorting of p3 is:" << double(end_time3-begin_time3) / (3000*CLOCKS_PER_SEC) << "s" << endl;
    clock_t begin_time4 = clock();
    for(int i=0;i<3000;i++){
        BSTSorting(p4,1);
    }
    clock_t end_time4 = clock();
    cout << "The average running time of the sorting of p4 is:" << double(end_time4-begin_time4) / (3000*CLOCKS_PER_SEC) << "s" << endl;

    //这一部分是异常情况的测试。
    //先编写一段寻找最大值的代码，其中包含二叉树为空的异常情况。
    //利用try与catch语句捕捉异常情况，并输出。
    try{
        BinarySearchTree<int> B;
        int i,k;
        cout << "We will find the maximal element of an integer array." << endl;
        cout << "Please enter the size of the array:" << endl;
        cin >> i;
        cout << "Please enter elements of the array." << endl;
        for(int j=0;j<i;j++){
            cin >> k;
            B.insert(k);
        }
        cout << "The maximal value is " << B.findMax() << endl;   
    }
    catch(char const*s){
        cout << s << endl;
    }
    //编写一段从10个节点的二叉树移走一个节点的代码，其中包含
    //需要移出的元素不存在的情况。
    //利用try和catch语句捕捉异常情况，并输出。
    try{
        BinarySearchTree<int> C;
        int k;
        cout << "Please enter 10 different integer elements of the binary tree." << endl;
        for(int i=0;i<10;i++){
            cin >> k;
            C.insert(k);
        }
        cout << "Please enter a value you want to remove." << endl;
        cin >> k;
        C.remove(k);
        cout << "This is the remain binary tree:" << endl;
        C.printTree();
    }
    catch(char const*s){
        cout << s << endl;
    }   

    return 0;
}